import java.util.*;

class Solution {
    //移动零
    public void moveZeroes(int[] nums) {
        for (int cur = 0, dest = -1; cur < nums.length; cur++) {
            if (nums[cur] != 0) {
                dest++;
                int tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
            }
        }
    }

    //复写零
    public void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = -1;
        int n = arr.length;
        while (cur < n) {
            if (arr[cur] != 0) dest++;
            else dest += 2;
            if (dest >= n - 1) break;
            cur++;
        }
        if (dest == n) {
            arr[n - 1] = 0;
            dest -= 2;
            cur--;
        }
        while (cur >= 0) {
            if (arr[cur] != 0) arr[dest--] = arr[cur--];
            else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }

    public void duplicateZeros1(int[] arr) {
        int[] arr1 = arr.clone();
        int cur = 0;
        int dest = 0;
        while (dest < arr.length) {
            if (arr1[cur] != 0) {
                arr[dest] = arr1[cur];
                dest++;
                cur++;
            } else {
                arr[dest] = arr1[cur];
                dest++;
                if (dest < arr.length) {
                    arr[dest] = arr1[cur];
                    dest++;
                }
                cur++;
            }
        }
    }

    //快乐数
    public int sum(int n) {
        int add = 0;
        while (n > 0) {
            int tmp = n % 10;
            add += tmp * tmp;
            n /= 10;
        }
        return add;
    }

    public boolean isHappy(int n) {
        int fast = sum(n);
        int node = n;
        while (node != fast) {
            fast = sum(sum(fast));
            node = sum(node);
        }
        return fast == 1;
    }

    //盛⽔最多的容器
    public int maxArea(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n - 1;
        int max = 0;
        while (left < right) {
            max = Math.max(max, (right - left) * Math.min(height[right], height[left]));
            if (height[left] > height[right]) right--;
            else left++;
        }
        return max;
    }

    //有效三⻆形的个数
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        int count = 0;
        Arrays.sort(nums);
        for (int i = n - 1; i >= 2; i--) {
            int right = i - 1;
            int left = 0;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    count += right - left;
                    right--;
                } else left++;
            }
        }
        return count;
    }

    //和为s的两个数字
    public int[] twoSum(int[] price, int target) {
        int n = price.length;
        int left = 0;
        int right = n - 1;
        while (left < right) {
            if (price[left] + price[right] > target) right--;
            else if (price[left] + price[right] < target) left++;
            else return new int[]{price[left], price[right]};
        }
        return new int[]{0};
    }

    //三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; ) {
            if (nums[i] > 0) break;
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else {
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[left], nums[right], nums[i])));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (right > left && nums[right] == nums[right + 1]) right--;
                }
            }
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }

    //四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < n; ) {
            for (int j = i + 1; j < n; ) {
                int left = j + 1, right = n - 1;
                long x = (long) target - (nums[j] + nums[i]);
                while (left < right) {
                    int sum = nums[right] + nums[left];
                    if (sum > x) right--;
                    else if (sum < x) left++;
                    else {
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[left], nums[right], nums[j], nums[i])));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }

    //⻓度最⼩的⼦数组
    public int minSubArrayLen(int target, int[] nums) {
        int ret = Integer.MAX_VALUE, sum = 0;
        for (int left = 0, right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                ret = Math.min(ret, right - left + 1);
                sum -= nums[left++];
            }
        }
        return ret > nums.length ? 0 : ret;
    }

    //⽆重复字符的最⻓⼦串
    public int lengthOfLongestSubstring(String s) {
        // int n = s.length(),ret = 0;
        // for(int i = 0;i < n;i++){
        //     int[] hash = new int[128];
        //     for(int j = i;j < n;j++){
        //         hash[s.charAt(j)]++;
        //         if(hash[s.charAt(j)]>1)break;
        //         ret = Math.max(ret,j-i+1);
        //     }
        // }
        // return ret;
        int n = s.length(), ret = 0;
        char[] ch = s.toCharArray();
        int[] hash = new int[128];
        for (int left = 0, right = 0; right < n; right++) {
            hash[ch[right]]++;
            while (hash[ch[right]] > 1) hash[ch[left++]]--;
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    //最⼤连续1的个数III
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int ret = 0;
        int count = 0;
        for (int left = 0, right = 0; right < n; right++) {
            if (nums[right] == 0) count++;
            while (count > k) if (nums[left++] == 0) count--;
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    //将x减到0的最⼩操作数
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int ret = -1, sum = 0;
        for (int i : nums) sum += i;
        sum -= x;
        if (sum < 0) return -1;
        for (int left = 0, right = 0, tmp = 0; right < n; right++) {
            tmp += nums[right];
            while (tmp > sum) tmp -= nums[left++];
            if (tmp == sum) ret = Math.max(ret, right - left + 1);

        }
        return ret == -1 ? -1 : n - ret;
    }

    //⽔果成篮
    public int totalFruit(int[] fruits) {
        int n = fruits.length, ret = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int left = 0, right = 0; right < n; right++) {
            map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
            while (map.size() > 2) {
                map.put(fruits[left], map.get(fruits[left]) - 1);
                if (map.get(fruits[left]) == 0) map.remove(fruits[left]);
                left++;
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    //找出所有⼦集的异或总和再求和
    int ret = 0;
    int path = 0;

    public int subsetXORSum(int[] nums) {
        dfs(nums, 0);
        return ret;
    }

    public void dfs(int[] nums, int i) {
        ret += path;
        for (int j = i; j < nums.length; j++) {
            path ^= nums[j];
            dfs(nums, j + 1);
            path ^= nums[j];
        }
    }

    //全排列Ⅱ
    /*List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int i){
        if(nums.length == i){
            ret.add(new ArrayList(path));
            return;
        }
        for(int j = 0;j < nums.length;j++){
            // if(check[j] == true || (j != 0 && nums[j] == nums[j-1] && check[j-1] == false))continue;
            // path.add(nums[j]);
            // check[j] = true;
            // dfs(nums,i+1);
            // path.remove(path.size()-1);
            // check[j] = false;
            if(check[j] == false && (j== 0 || nums[j]!=nums[j-1] || check[j-1] == true)){
                path.add(nums[j]);
                check[j] = true;
                dfs(nums,i+1);
                path.remove(path.size()-1);
                check[j] = false;
            }
        }
    }*/
    //最⼩覆盖⼦串
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int m = s.length, n = t.length;
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        int minlen = Integer.MAX_VALUE, state = -1;
        for (char ch : t) map1.put(ch, map1.getOrDefault(ch, 0) + 1);
        for (int left = 0, right = 0, count = 0; right < m; right++) {
            map2.put(s[right], map2.getOrDefault(s[right], 0) + 1);
            if (map2.get(s[right]).equals(map1.getOrDefault(s[right], 0))) count++;
            while (count == map1.size()) {
                if (right - left + 1 < minlen) {
                    state = left;
                    minlen = right - left + 1;
                }
                if (map2.get(s[left]).equals(map1.getOrDefault(s[left], 0))) count--;
                map2.put(s[left], map2.get(s[left]) - 1);
                left++;
            }
        }
        return state == -1 ? "" : ss.substring(state, state + minlen);
        // int[] hash1 = new int[128];
        // int[] hash2 = new int[128];
        // int kinds = 0;
        // for(char ch:t)if(hash1[ch]++ == 0)kinds++;
        // for(int left = 0,right = 0,count = 0;right<m;right++){
        //     char in = s[right];
        //     if(++hash2[in] == hash1[in])count++;
        //     while(count==kinds){
        //         if(right-left+1<minlen){
        //             minlen = right-left+1;
        //             state = left;
        //         }
        //         char out = s[left++];
        //         if(hash2[out]-- == hash1[out])count--;
        //     }
        // }
        // return state==-1 ? "" : ss.substring(state,state+minlen);
    }

    //⼆分查找
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int min = (right - left) / 2 + left;
            if (nums[min] > target) right = min - 1;
            else if (nums[min] < target) left = min + 1;
            else return min;
        }
        return -1;
    }

    //在排序数组中查找元素的第⼀个和最后⼀个位置
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if (n == 0) return ret;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int num = nums[mid];
            if (num >= target)
                right = mid;
            else left = mid + 1;
        }
        if (nums[left] != target) return ret;
        ret[0] = left;
        left = 0;
        right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            int num = nums[mid];
            if (num > target)
                right = mid - 1;
            else left = mid;
        }
        ret[1] = right;
        return ret;
    }

    //搜索插⼊位置
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    //x的平⽅根
    public int mySqrt(int x) {
        if (x < 1) return 0;
        long left = 1, right = x;
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid > x) right = mid - 1;
            else left = mid;
        }
        return (int) left;
    }

    //⼭峰数组的峰顶
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] > arr[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    //寻找峰值
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if (nums[mid] > nums[mid - 1]) left = mid;
            else right = mid - 1;
        }
        return left;
    }

    //搜索旋转排序数组中的最⼩值
    public int findMin(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if (nums[mid] < nums[0]) right = mid - 1;
            else left = mid;
        }
        return right + 1 >= n ? nums[0] : nums[right + 1];
    }

    //0〜n-1中缺失的数字
    public int takeAttendance(int[] records) {
        int n = records.length;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid == records[mid]) left = mid + 1;
            else right = mid;
        }
        return left == records[left] ? left + 1 : left;
    }

    //【模板】⼀维前缀和
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        long[] arr = new long[n];
        long[] dp = new long[n + 1];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            dp[i + 1] = arr[i] + dp[i];
        }
        while (q-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(dp[b] - dp[a - 1]);
        }
    }

    //【模板】⼆维前缀和
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        int[][] arr = new int[n][m];
        long[][] dp = new long[n + 1][m + 1];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                arr[i][j] = in.nextInt();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = arr[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];

        while (q-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            int d = in.nextInt();
            System.out.println(dp[c][d] + dp[a - 1][b - 1] - dp[a - 1][d] - dp[c][b - 1]);
        }
    }

    //寻找数组的中⼼下标
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1] + nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) g[i] = g[i + 1] + nums[i + 1];
        for (int i = 0; i < n; i++) {
            if (f[i] == g[i]) return i;
        }
        return -1;
    }

    //除⾃⾝以外数组的乘积
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = g[n - 1] = 1;
        int[] ret = new int[n];
        for (int i = 1; i < n; i++) f[i] = f[i - 1] * nums[i - 1];
        for (int i = n - 2; 0 <= i; i--) g[i] = g[i + 1] * nums[i + 1];
        for (int i = 0; i < n; i++) ret[i] = f[i] * g[i];
        return ret;
    }

    //和为k的⼦数组
    public int subarraySum(int[] nums, int k) {
        int n = nums.length, ret = 0, sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i : nums) {
            sum += i;
            ret += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }

    //和可被K整除的⼦数组
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length;
        int ret = 0, sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0 % k, 1);
        for (int i : nums) {
            sum += i;
            int r = (sum % k + k) % k;
            ret += map.getOrDefault(r, 0);
            map.put(r, map.getOrDefault(r, 0) + 1);
        }
        return ret;
    }

    //连续数组
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int ret = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (nums[i] == 0) ? -1 : 1;
            if (map.containsKey(sum)) ret = Math.max(ret, i - map.get(sum));
            else map.put(sum, i);
        }
        return ret;
    }

    //矩阵区域和
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] ret = new int[m][n];
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                int x1 = Math.max(0, i - k) + 1;
                int y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(m - 1, i + k) + 1;
                int y2 = Math.min(n - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
            }
        return ret;
    }

    //判断字符是否唯⼀
    public boolean isUnique(String astr) {
        if (astr.length() > 26) return false;
        int bitMap = 0;
        for (int i = 0; i < astr.length(); i++) {
            int x = astr.charAt(i) - 'a';
            if (((bitMap >> x) & 1) == 1) return false;
            bitMap |= 1 << x;
        }
        return true;
    }

    //丢失的数字
    public int missingNumber(int[] nums) {
        int ret = 0, i = 0;
        for (; i < nums.length; i++) {
            ret = ret ^ nums[i] ^ i;
        }
        return ret ^ i;
    }

    //两整数之和
    public int getSum(int a, int b) {
        while (b != 0) {
            int tmp = a ^ b;
            b = (a & b) << 1;
            a = tmp;
        }
        return a;
    }

    //只出现⼀次的数字II
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int x : nums) sum += (x >> i) & 1;
            ret |= (sum % 3 << i);
        }
        return ret;
    }

    //消失的两个数字
    public int[] missingTwo(int[] nums) {
        int tmp = 0;
        for (int i = 1; i <= nums.length + 2; i++) tmp ^= i;
        for (int i : nums) tmp ^= i;
        tmp = tmp == Integer.MAX_VALUE ? tmp : tmp & (-tmp);
        int m = 0, n = 0;
        for (int i : nums)
            if ((tmp & i) != 0) m ^= i;
            else n ^= i;
        for (int i = 1; i <= nums.length + 2; i++)
            if ((tmp & i) != 0) m ^= i;
            else n ^= i;
        return new int[]{m, n};
    }

    //替换所有的问号
    public String modifyString(String s) {
        char[] x = s.toCharArray();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (x[i] == '?') {
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if ((i == 0 || x[i - 1] != ch) && (i == n - 1 || x[i + 1] != ch)) {
                        x[i] = ch;
                        break;
                    }
                }
            }
        }
        return String.valueOf(x);
    }

    //提莫攻击
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int sum = 0;
        for (int i = 1; i < timeSeries.length; i++) {
            if (timeSeries[i] - timeSeries[i - 1] >= duration) {
                sum += duration;
            } else {
                sum += timeSeries[i] - timeSeries[i - 1];
            }
        }
        return sum + duration;
    }

    //N字形变换
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        int n = s.length();
        StringBuilder ret = new StringBuilder();
        int d = 2 * numRows - 2;
        for (int i = 0; i < n; i += d) ret.append(s.charAt(i));
        for (int k = 1; k < numRows - 1; k++) {
            for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {
                if (i < n) ret.append(s.charAt(i));
                if (j < n) ret.append(s.charAt(j));
            }
        }
        for (int i = numRows - 1; i < n; i += d) ret.append(s.charAt(i));
        return ret.toString();
    }

    //外观数列
    public String countAndSay(int n) {
        String ret = "1";
        for (int i = 1; i < n; i++) {
            StringBuilder str = new StringBuilder();
            for (int left = 0, right = 0; right < ret.length(); ) {
                while (right < ret.length() && ret.charAt(left) == ret.charAt(right)) right++;
                str.append(Integer.toString(right - left));
                str.append(ret.charAt(left));
                left = right;
            }
            ret = str.toString();
        }
        return ret;
    }

    //数⻘蛙
    public int minNumberOfFrogs(String croakOfFrogs) {
        HashMap<Character, Integer> map = new HashMap<>();
        char[] s = {'c', 'r', 'o', 'a', 'k'};
        char[] ch = croakOfFrogs.toCharArray();
        int[] hash = new int[s.length];
        for (int i = 0; i < s.length; i++) map.put(s[i], i);
        for (char x : ch) {
            if (x == s[0]) {
                if (hash[s.length - 1] != 0) hash[s.length - 1]--;
                hash[0]++;
            } else {
                int index = map.get(x);
                if (hash[index - 1] == 0) return -1;
                hash[index]++;
                hash[index - 1]--;
            }
        }
        for (int i = 0; i < s.length - 1; i++)
            if (hash[i] != 0) return -1;
        return hash[s.length - 1];
    }

    //颜⾊分类
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public void sortColors(int[] nums) {
        int left = -1;
        int right = nums.length;
        for (int i = 0; i < right; ) {
            if (nums[i] == 0) {
                swap(nums, ++left, i++);
            } else if (nums[i] == 2) {
                swap(nums, --right, i);
            } else {
                i++;
            }
        }
    }

    //快速排序
/*    public void swap(int[] nums ,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }*/
    public void qsort(int[] nums, int l, int r) {
        if (l >= r) return;
        int left = l - 1;
        int right = r + 1;
        int key = nums[new Random().nextInt(r - l + 1) + l];
        int i = l;
        while (i < right) {
            if (nums[i] < key) swap(nums, ++left, i++);
            else if (nums[i] > key) swap(nums, --right, i);
            else i++;
        }
        qsort(nums, l, left);
        qsort(nums, right, r);
    }

    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }
    //快速选择算法
//    public void swap(int[] nums, int i, int j) {
//        int tmp = nums[i];
//        nums[i] = nums[j];
//        nums[j] = tmp;
//    }

    public int qsort(int[] nums, int l, int r, int k) {
        if (l == r) return nums[l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        int key = nums[new Random().nextInt(r - l + 1) + l];
        while (i < right) {
            if (nums[i] < key)
                swap(nums, ++left, i++);
            else if (nums[i] > key)
                swap(nums, --right, i);
            else
                i++;
        }
        int b = right - left - 1;
        int c = r - right + 1;
        if (c >= k)
            return qsort(nums, right, r, k);
        else if (b + c >= k)
            return key;
        else
            return qsort(nums, l, left, k - b - c);
    }


    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }

    //最⼩的k个数
/*    public void qsort(int[] nums,int l,int r,int k){
        if(l >= r)return;
        int i = l;
        int left = l - 1;
        int right = r + 1;
        int key = nums[new Random().nextInt(r - l + 1) + l];
        while(i < right){
            if(nums[i] < key)swap(nums,++left,i++);
            else if(nums[i] == key)i++;
            else swap(nums,--right,i);
        }
        int a = left - l + 1, b = right - left - 1;
        if(a > k) qsort(nums, l, left, k);
        else if(a + b >= k) return;
        else qsort(nums, right, r, k - a - b);
    }*/

/*    public void swap(int[] nums,int a,int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }*/

    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock, 0, stock.length - 1, cnt);
        int[] ret = new int[cnt];
        for (int i = 0; i < cnt; i++) ret[i] = stock[i];
        return ret;
    }

    //归并排序
    //public void swap(int[] nums ,int i,int j){
    //        int tmp = nums[i];
    //        nums[i] = nums[j];
    //        nums[j] = tmp;
    //    }
    //    public void qsort(int[] nums ,int l,int r){
    //        if(l >= r)return;
    //        int left = l - 1;
    //        int right = r + 1;
    //        int key = nums[new Random().nextInt(r-l+1)+l];
    //        int i = l;
    //        while(i < right){
    //            if(nums[i] < key)swap(nums,++left,i++);
    //            else if(nums[i] > key)swap(nums,--right,i);
    //            else i++;
    //        }
    //        qsort(nums, l, left);
    //        qsort(nums, right, r);
    //    }
    //    public int[] sortArray(int[] nums) {
    //        qsort(nums,0,nums.length-1);
    //        return nums;
    //    }
//    int[] tmp;
//    public void mergeSort(int[] nums,int left,int right){
//        if(left >= right)return;
//        int mid = (right + left)/2;
//        mergeSort(nums,left,mid);
//        mergeSort(nums,mid+1,right);
//        int cur1 = left;
//        int cur2 = mid+1;
//        int i = 0;
//        while(cur1 <= mid && cur2 <= right){
//            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
//        }
//        while(cur1 <= mid)tmp[i++] = nums[cur1++];
//        while(cur2 <= right)tmp[i++] = nums[cur2++];
//        for(int j = left;j <= right;j++)nums[j] = tmp[j-left];
//    }
//
//    public int[] sortArray(int[] nums) {
//        tmp = new int[nums.length];
//        mergeSort(nums,0,nums.length-1);
//        return nums;
//    }
    //数组中的逆序对
    int[] tmp;

    public int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        int ret = 0;
        int mid = (left + right) / 2;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        //升序
        // while(cur1 <= mid && cur2 <= right){
        //     if(nums[cur1] <= nums[cur2]){
        //         tmp[i++] = nums[cur1++];
        //     }else{
        //         ret += mid - cur1 + 1;
        //         tmp[i++] = nums[cur2++];
        //     }
        // }
        //降序
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] > nums[cur2]) {
                ret += right - cur2 + 1;
                tmp[i++] = nums[cur1++];
            } else {
                tmp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];
        for (int j = left; j <= right; j++) nums[j] = tmp[j - left];
        return ret;
    }

    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        return mergeSort(record, 0, record.length - 1);
    }
    //计算右侧⼩于当前元素的个数
//    int[] tmp1;
//    int[] tmp2;
//    int[] ret;
//    int[] index;
//    public void mergeSort(int[] nums,int left,int right){
//        if(left >= right)return;
//        int mid = (left + right)/2;
//        mergeSort(nums,left,mid);
//        mergeSort(nums,mid + 1,right);
//        int cur1 = left,i = 0,cur2 = mid + 1;
//        while(cur1 <= mid && cur2 <= right){
//            if(nums[cur1] > nums[cur2]){
//                ret[index[cur1]] += right - cur2 + 1;
//                tmp1[i] = nums[cur1];
//                tmp2[i++] = index[cur1++];
//            }else{
//                tmp2[i] = index[cur2];
//                tmp1[i++] = nums[cur2++];
//            }
//        }
//        while(cur1 <= mid){
//            tmp2[i] = index[cur1];
//            tmp1[i++] = nums[cur1++];
//        }
//        while(cur2 <= right){
//            tmp2[i] = index[cur2];
//            tmp1[i++] = nums[cur2++];
//        }
//        for(int j = left;j <= right;j++){
//            nums[j] = tmp1[j-left];
//            index[j] = tmp2[j-left];
//        }
//    }
//    public List<Integer> countSmaller(int[] nums) {
//        tmp1 = new int[nums.length];
//        tmp2 = new int[nums.length];
//        index = new int[nums.length];
//        for(int i = 0;i < nums.length;i++)index[i] = i;
//        ret = new int[nums.length];
//        mergeSort(nums,0,nums.length-1);
//        List<Integer> l = new ArrayList<Integer>();
//        for(int x : ret)l.add(x);
//        return l;
//    }
    //翻转对
//    int[] tmp;
//    public int mergeSort(int[] nums,int left,int right){
//        if(left >= right)return 0;
//        int ret = 0;
//        int mid = (left + right)/2;
//        ret += mergeSort(nums,left,mid);
//        ret += mergeSort(nums,mid + 1,right);
//        int cur1 = left,i = 0,cur2 = mid + 1;
//        //降序
//        // while(cur2 <= right){
//        //     while(cur1 <= mid && nums[cur1]/2.0 > nums[cur2]){
//        //         if(cur1 > mid)break;
//        //         ret += right - cur2 + 1;
//        //         cur1++;
//        //     }
//        //     cur2++;
//        // }
//        // // while(cur1 <= mid){
//        // //     while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
//        // //         if(cur2 > right)break;
//        // //         ret += right - cur2 + 1;
//        // //         cur1++;
//        // //     }
//        // // }
//        // cur1 = left;
//        // cur2 = mid + 1;
//        // while(cur1 <= mid && cur2 <= right){
//        //     if(nums[cur1] > nums[cur2]){
//        //         tmp[i++] = nums[cur1++];
//        //     }else{
//        //         tmp[i++] = nums[cur2++];
//        //     }
//        // }
//        //升序
//        // while(cur1 <= mid){
//        //     while(cur2 <= right && nums[cur1]/2.0 > nums[cur2]){
//        //         if(cur2 > right)break;
//        //         ret += mid - cur1 + 1;
//        //         cur2++;
//        //     }
//        //     cur1++;
//        // }
//        while(cur2 <= right){
//            while(cur1 <= mid && nums[cur1]/2.0 <= nums[cur2])cur1++;
//            if(cur2 > right)break;
//            ret += mid - cur1 + 1;
//            cur2++;
//        }
//        cur1 = left;
//        cur2 = mid + 1;
//        while(cur1 <= mid && cur2 <= right){
//            if(nums[cur1] > nums[cur2]){
//                tmp[i++] = nums[cur2++];
//            }else{
//                tmp[i++] = nums[cur1++];
//            }
//        }
//
//        while(cur1 <= mid){
//            tmp[i++] = nums[cur1++];
//        }
//        while(cur2 <= right){
//            tmp[i++] = nums[cur2++];
//        }
//        for(int j = left;j <= right;j++){
//            nums[j] = tmp[j-left];
//        }
//        return ret;
//    }
//    public int reversePairs(int[] nums) {
//        int n = nums.length;
//        tmp = new int[n];
//        return mergeSort(nums,0,n-1);
//    }
    //两数相加

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
/*    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode list = new ListNode(-1);
        ListNode head = list;
        int t = 0;
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        // while(cur1 != null && cur2 != null){
        //     t += cur1.val + cur2.val;
        //     list.next = new ListNode(t % 10);
        //     cur1 = cur1.next;
        //     cur2 = cur2.next;
        //     list = list.next;
        //     t /= 10;
        // }
        // while(cur1 != null){
        //     t += cur1.val;
        //     cur1 = cur1.next;
        //     list.next = new ListNode(t % 10);
        //     list = list.next;
        //     t /= 10;
        // }
        // while(cur2 != null){
        //     t += cur2.val;
        //     cur2 = cur2.next;
        //     list.next = new ListNode(t % 10);
        //     list = list.next;
        //     t /= 10;
        // }
        // if(t != 0)list.next = new ListNode(t % 10);
        while(cur1 != null || cur2 != null || t != 0){
            if(cur1 != null){
                t += cur1.val;
                cur1 = cur1.next;
            }
            if(cur2 != null){
                t += cur2.val;
                cur2 = cur2.next;
            }
            list.next = new ListNode(t % 10);
            t /= 10;
            list = list.next;
        }
        return head.next;
    }*/
    //两两交换链表中的节点
//    public ListNode swapPairs(ListNode head) {
//        if(head == null || head.next == null)return head;
//        ListNode newhead = new ListNode(-1);
//        newhead.next = head;
//        ListNode prev = newhead;
//        ListNode cur = head;
//        ListNode curN = head.next;
//        ListNode curNN = head.next.next;
//        while(cur != null && curN != null){
//            prev.next = curN;
//            curN.next = cur;
//            cur.next = curNN;
//            prev = cur;
//            cur = curNN;
//            if(cur != null)curN = cur.next;
//            if(curN != null)curNN = curN.next;
//        }
//        return newhead.next;
//    }
    //重排链表

    //Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return;
        ListNode head1 = head;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //ListNode head2 = new ListNode(-1);
        ListNode head2 = null;
        ListNode cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            //cur.next = head2.next;
            cur.next = head2;
            head2 = cur;
            //head2.next = cur;
            cur = next;
        }
        ListNode cur1 = head1;
        //ListNode cur2 = head2.next;
        ListNode cur2 = head2;
        //ListNode prev = new ListNode(-1);
        // while(cur1 != null){
        //     prev.next = cur1;
        //     prev = cur1;
        //     cur1 = cur1.next;
        //     if(cur2 != null){
        //         prev.next = cur2;
        //         prev = cur2;
        //         cur2 = cur2.next;
        //     }
        // }
        while (cur1 != null && cur2 != null) {
            ListNode next1 = cur1.next;
            ListNode next2 = cur2.next;
            cur1.next = cur2;
            cur2.next = next1;
            cur1 = next1;
            cur2 = next2;
        }
    }

    //合并K个升序链表
    public ListNode func(ListNode[] lists, int left, int right) {
        if (left > right) return null;
        if (left == right) return lists[left];
        int mid = (left + right) / 2;
        ListNode l1 = func(lists, left, mid);
        ListNode l2 = func(lists, mid + 1, right);
        return fun(l1, l2);
    }

    public ListNode fun(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode ret = new ListNode(-1);
        ListNode prev = ret;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                prev = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                prev = l2;
                l2 = l2.next;
            }
        }
        if (l1 != null) prev.next = l1;
        if (l2 != null) prev.next = l2;
        return ret.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        // PriorityQueue<ListNode> queue = new PriorityQueue<>((v1,v2) -> v1.val - v2.val);
        // for(ListNode cur : lists)
        //     if(cur != null)queue.offer(cur);
        // ListNode ret = new ListNode(-1);
        // ListNode prev = ret;
        // while(!queue.isEmpty()){
        //     ListNode t = queue.poll();
        //     prev.next = t;
        //     prev = t;
        //     if(t.next != null)queue.offer(t.next);
        // }
        // return ret.next;
        return func(lists, 0, lists.length - 1);
    }

    //K个⼀组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        int n = len / k;
        if (n == 0) return head;
        ListNode newhead = new ListNode(-1);
        ListNode prev = newhead;
        cur = head;
        for (int i = 0; i < n; i++) {
            ListNode tmp = cur;
            int count = k;
            while (count-- > 0) {
                ListNode next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev.next = cur;
        return newhead.next;
    }

    //两数之和
/*    public int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            int a = target - nums[i];
            if(map.containsKey(a)){
                ret[0] = i;
                ret[1] = map.get(a);
                break;
            }
            map.put(nums[i],i);
        }
        // HashMap<Integer,Integer> map = new HashMap<>();
        // for(int i = 0;i < nums.length;i++)map.put(nums[i],i);
        // for(int i = 0;i < nums.length;i++){
        //     int a = target - nums[i];
        //     if(a == nums[i] && map.get(a) == i){
        //         continue;
        //     }
        //     if(map.containsKey(a)){
        //         ret[0] = i;
        //         ret[1] = map.get(a);
        //         break;
        //     }
        // }
        //暴力枚举
        // for(int i = 1;i < nums.length;i++){
        //     for(int j = i -1;j >= 0;j--){
        //         if(nums[j] + nums[i] == target){
        //             ret[0] = i;
        //             ret[1] = j;
        //             break;
        //         }
        //     }
        // }
        return ret;
    }*/
    //判断是否互为字符重排
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int[] hash = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            hash[s1.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s1.length(); i++) {
            if (--hash[s2.charAt(i) - 'a'] < 0) return false;
        }
        return true;
    }

    //存在重复元素I
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
                continue;
            }
            return true;
        }
        return false;
    }

    //存在重复元素II
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }

    //字⺟异位词分组
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] ch = s.toCharArray();
            Arrays.sort(ch);
            String key = new String(ch);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList());
            }
            map.get(key).add(s);
        }
        return new ArrayList(map.values());
    }

    //最⻓公共前缀
    public String longestCommonPrefix(String[] strs) {
        //分开比较
        int ret = Integer.MAX_VALUE;
        char[] s1 = strs[0].toCharArray();
        for (int j = 0; j < strs.length; j++) {
            int i = 0;
            char[] s2 = strs[j].toCharArray();
            int len = Math.min(strs[0].length(), strs[j].length());
            while (i < len) {
                if (s1[i] == s2[i]) i++;
                else {
                    len = i;
                    break;
                }
            }
            ret = Math.min(ret, i);
        }
        return ret < 0 ? null : strs[0].substring(0, ret);
        //统一比较
        // char[] s = strs[0].toCharArray();
        // for(int i = 0;i < s.length;i++){
        //     for(int j = 1;j < strs.length;j++){
        //         if(i == strs[j].length() || s[i] != strs[j].charAt(i)){
        //             return strs[0].substring(0,i);
        //         }
        //     }
        // }
        // return strs[0];
    }

    //最⻓回⽂⼦串
    public String longestPalindrome(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        int len = 1, begin = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (ch[i] == ch[j]) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                if (dp[i][j] && j - i + 1 > len) {
                    len = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + len);
    }

    //⼆进制求和
    public String addBinary(String a, String b) {
        StringBuilder ret = new StringBuilder();
        int cur1 = a.length() - 1;
        int cur2 = b.length() - 1;
        int sum = 0;
        while (cur1 >= 0 || cur2 >= 0 || sum != 0) {
            if (cur1 >= 0) sum += a.charAt(cur1--) - '0';
            if (cur2 >= 0) sum += b.charAt(cur2--) - '0';
            ret.append(sum % 2);
            sum /= 2;
        }
        return ret.reverse().toString();
    }

    //字符串相乘
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        boolean flag = true;
        StringBuilder ret = new StringBuilder();
        num1 = new StringBuilder(num1).reverse().toString();
        num2 = new StringBuilder(num2).reverse().toString();
        int[] tmp = new int[m + n - 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                if (tmp[i + j] != 0) flag = false;
            }
        }
        if (flag) return "0";
        int k = 0;
        int sum = 0;
        while (k < m + n - 1 || sum != 0) {
            if (k < m + n - 1) sum += tmp[k++];
            ret.append(sum % 10);
            sum /= 10;
        }
        return ret.reverse().toString();
    }

    //删除字符中的所有相邻重复项
    public String removeDuplicates(String s) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (str.length() > 0 && str.toString().charAt(str.length() - 1) == s.charAt(i)) {
                str.deleteCharAt(str.length() - 1);
            } else {
                str.append(s.charAt(i));
            }
        }
        return str.toString();
    }

    //⽐较含退格的字符串
    public boolean backspaceCompare(String ss, String tt) {
        StringBuilder s = new StringBuilder();
        StringBuilder t = new StringBuilder();
        for (int i = 0; i < ss.length(); i++) {
            if (ss.charAt(i) == '#') {
                if (s.length() > 0) s.deleteCharAt(s.length() - 1);
            } else {
                s.append(ss.charAt(i));
            }
        }
        for (int i = 0; i < tt.length(); i++) {
            if (tt.charAt(i) == '#') {
                if (t.length() > 0) t.deleteCharAt(t.length() - 1);
            } else {
                t.append(tt.charAt(i));
            }
        }
        return s.toString().equals(t.toString());
    }

    //字符串解码
    public String decodeString(String _s) {
        Stack<String> str = new Stack<>();
        str.push("");
        Stack<Integer> num = new Stack<>();
        int i = 0, n = _s.length();
        char[] c = _s.toCharArray();
        while (i < n) {
            if (c[i] == '[') {
                StringBuilder s = new StringBuilder();
                i++;
                while (i < n && c[i] >= 'a' && c[i] <= 'z') {
                    s.append(c[i]);
                    i++;
                }
                str.push(s.toString());
            } else if (c[i] == ']') {
                String s1 = str.pop();
                String s2 = new String();
                int m = num.pop();
                for (int j = 0; j < m; j++) {
                    s2 += s1;
                }
                str.push(str.pop() + s2);
                i++;
            } else if (c[i] >= '0' && c[i] <= '9') {
                int tmp = 0;
                while (i < n && c[i] >= '0' && c[i] <= '9') {
                    tmp = tmp * 10 + (c[i] - '0');
                    i++;
                }
                num.push(tmp);
            } else {
                String s1 = str.pop();
                StringBuilder s = new StringBuilder();
                while (i < n && c[i] >= 'a' && c[i] <= 'z') {
                    s.append(c[i]);
                    i++;
                }
                str.push(s1 + s.toString());
            }
        }
        return str.pop();
    }

    //验证栈序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> st = new Stack<>();
        int j = 0;
        for (int n : pushed) {
            st.push(n);
            while (!st.empty() && st.peek() == popped[j]) {
                st.pop();
                j++;
            }
        }
        return st.empty();
    }

    //N叉树的层序遍历
    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int n = q.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                Node t = q.poll();
                tmp.add(t.val);
                // for(Node child : t.children){
                //     if(child != null)q.offer(child);
                // }
                for (int j = 0; j < t.children.size(); j++) {
                    if (t.children.get(j) != null) q.offer(t.children.get(j));
                }
            }
            ret.add(tmp);
        }
        return ret;
    }

    //⼆叉树的锯⻮形层序遍历
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean flag = true;
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> l = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                if (flag) l.add(cur.val);
                else l.add(0, cur.val);
                if (cur.left != null) {
                    q.add(cur.left);
                }
                if (cur.right != null) {
                    q.add(cur.right);
                }
            }
            ret.add(l);
            if (flag) flag = false;
            else flag = true;
        }
        return ret;
    }
    //72.
}